#include <bits/stdc++.h>
using namespace std;

/*
2257. 统计网格图中没有被保卫的格子数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。

一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。

请你返回空格子中，有多少个格子是 没被保卫 的。

 

示例 1：



输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
输出：7
解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子，所以我们返回 7 。
示例 2：



输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
输出：4
解释：上图中，没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子，所以我们返回 4 。
 

提示：

1 <= m, n <= 105
2 <= m * n <= 105
1 <= guards.length, walls.length <= 5 * 104
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= rowi, rowj < m
0 <= coli, colj < n
guards 和 walls 中所有位置 互不相同 。
*/

// 法一
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        // net status
        vector<vector<int>> grid(m, vector<int>(n, 0));
        // flag wall guard
        for (auto& g : guards) {
            int x = g[0], y = g[1];
            grid[x][y] = 1;
        }
        for (auto& w : walls) {
            int x = w[0], y = w[1];
            grid[x][y] = 2;
        }

        // dirs  edges
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // foreach guards  给in range的flag
        for (auto& g : guards) {
            int x = g[0], y = g[1];
            for (auto& [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                // 当前方向  until out of eage
                while (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (grid[nx][ny] == 1 || grid[nx][ny] == 2) break;  // 障碍挡住视线，停止延伸
                    if (grid[nx][ny] == 0)  grid[nx][ny] = 3;
                    // move again
                    nx += dx;
                    ny += dy;
                }
            }
        }
        // cnt total
        int ans = 0;
        for (auto& row : grid) {
            for (int val : row) {
                if (val == 0)   ans++;
            }
        }
        return ans;
    }
};

// 法二
class Solution {
    // 四方向：左、右、上、下（编译期常量，访问高效）
    static constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards,
                       vector<vector<int>>& walls) {
        // 网格：0=未保卫空格，1=被保卫，-1=障碍（警卫/墙）
        // int8_t 仅占1字节，比int节省内存，提升缓存命中率
        vector guarded(m, vector<int8_t>(n));

        // 统一标记障碍（警卫和墙均设为-1，简化后续判断）
        for (auto& g : guards) {
            guarded[g[0]][g[1]] = -1;
        }
        for (auto& w : walls) {
            guarded[w[0]][w[1]] = -1;
        }

        // 遍历每个警卫，向四方向扩散标记被保卫格子
        for (auto& g : guards) {
            for (auto& [dx, dy] : DIRS) {
                int x = g[0] + dx, y = g[1] + dy;
                // 沿当前方向延伸，出界或遇障碍（-1）则停止
                while (0 <= x && x < m && 0 <= y && y < n && guarded[x][y] != -1) {
                    guarded[x][y] = 1; // 标记为被保卫
                    x += dx; // 继续沿方向移动
                    y += dy;
                }
            }
        }

        // 统计未被保卫的空格（值为0），ranges::count 高效计数
        int ans = 0;
        for (auto& row : guarded) {
            ans += ranges::count(row, 0);
        }
        return ans;
    }
};